
 <!DOCTYPE HTML>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
  
    <title>全排列和全组合实现 | Jark&#39;s Blog</title>
    <meta name="viewport" content="width=device-width, initial-scale=1,user-scalable=no">
    
    <meta name="author" content="WuChong">
    
    <meta name="description" itemprop="description" content="记得 @老赵 之前在微博上吐槽说，“有的人真是毫无长进，六年前某同事不会写程序输出全排列，昨天发邮件还是问我该怎么写，这时间浪费到我都看不下去了。” 那时候就很好奇全排列到底是什么东西，到底有多难？今天复习的时候终于碰到这题了，结果果然自己太渣，看了好久都没明白，代码实现又是磕磕碰碰的。所以，就把它整理成笔记加深记忆，也希望能帮到和我一样的人。">
    
    
    <meta name="description" content="记得 @老赵 之前在微博上吐槽说，“有的人真是毫无长进，六年前某同事不会写程序输出全排列，昨天发邮件还是问我该怎么写，这时间浪费到我都看不下去了。” 那时候就很好奇全排列到底是什么东西，到底有多难？今天复习的时候终于碰到这题了，结果果然自己太渣，看了好久都没明白，代码实现又是磕磕碰碰的。所以，就把它整理成笔记加深记忆，也希望能帮到和我一样的人。">
<meta property="og:type" content="article">
<meta property="og:title" content="全排列和全组合实现">
<meta property="og:url" content="http://wuchong.me/blog/2014/07/28/permutation-and-combination-realize/">
<meta property="og:site_name" content="Jark's Blog">
<meta property="og:description" content="记得 @老赵 之前在微博上吐槽说，“有的人真是毫无长进，六年前某同事不会写程序输出全排列，昨天发邮件还是问我该怎么写，这时间浪费到我都看不下去了。” 那时候就很好奇全排列到底是什么东西，到底有多难？今天复习的时候终于碰到这题了，结果果然自己太渣，看了好久都没明白，代码实现又是磕磕碰碰的。所以，就把它整理成笔记加深记忆，也希望能帮到和我一样的人。">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="全排列和全组合实现">
<meta name="twitter:description" content="记得 @老赵 之前在微博上吐槽说，“有的人真是毫无长进，六年前某同事不会写程序输出全排列，昨天发邮件还是问我该怎么写，这时间浪费到我都看不下去了。” 那时候就很好奇全排列到底是什么东西，到底有多难？今天复习的时候终于碰到这题了，结果果然自己太渣，看了好久都没明白，代码实现又是磕磕碰碰的。所以，就把它整理成笔记加深记忆，也希望能帮到和我一样的人。">
<meta name="twitter:creator" content="@jarkwu">
<link rel="publisher" href="111190881341800841449">

    
    <link rel="alternative" href="/atom.xml" title="Jark&#39;s Blog" type="application/atom+xml">
    
    
    <link rel="icon" href="/img/favicon.ico">
    
    
    <link rel="apple-touch-icon" href="/img/jacman.jpg">
    <link rel="apple-touch-icon-precomposed" href="/img/jacman.jpg">
    
    <link rel="stylesheet" href="/css/style.css" type="text/css">
</head>

  <body>
    <header>
      <div>
		
			<div id="imglogo">
				<a href="/"><img src="/img/logo.png" alt="Jark&#39;s Blog" title="Jark&#39;s Blog"/></a>
			</div>
			
			<div id="textlogo">
				<h1 class="site-name"><a href="/" title="Jark&#39;s Blog">Jark&#39;s Blog</a></h1>
				<h2 class="blog-motto">当你的才华还撑不起你的野心时，你就应该静下心来学习。</h2>
			</div>
			<div class="navbar"><a class="navbutton navmobile" href="#" title="菜单">
			</a></div>
			<nav class="animated">
				<ul>
					<ul>
					 
						<li><a href="/">首页</a></li>
					
						<li><a href="/archives">归档</a></li>
					
						<li><a href="/about">关于</a></li>
					
					<li>
 					
						<form class="search" action="http://zhannei.baidu.com/cse/search" target="_blank">
							<label>Search</label>
						<input name="s" type="hidden" value= 783281470518440642 ><input type="text" name="q" size="30" placeholder="搜索"><br>
						</form>
					
					</li>
				</ul>
			</nav>			
</div>
    </header>
    <div id="container">
      <div id="main" class="post" itemscope itemprop="blogPost">
  
	<article itemprop="articleBody"> 
		<header class="article-info clearfix">
  <h1 itemprop="name">
    
      <a href="/blog/2014/07/28/permutation-and-combination-realize/" title="全排列和全组合实现" itemprop="url">全排列和全组合实现</a>
  </h1>
  <p class="article-author">By
       
		<a href="https://plus.google.com/111190881341800841449?rel=author" title="WuChong" target="_blank" itemprop="author">WuChong</a>
		
  <p class="article-time">
    <time datetime="2014-07-28T01:41:18.000Z" itemprop="datePublished"> 发表于 2014-07-28</time>
    
  </p>
</header>
	<div class="article-content">
		
		<div id="toc" class="toc-article">
			<strong class="toc-title">文章目录</strong>
		
			<ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#全排列"><span class="toc-number">1.</span> <span class="toc-text">全排列</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#去重的全排列"><span class="toc-number">2.</span> <span class="toc-text">去重的全排列</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#全组合"><span class="toc-number">3.</span> <span class="toc-text">全组合</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#参考资料"><span class="toc-number">4.</span> <span class="toc-text">参考资料</span></a></li></ol>
		
		</div>
		
		<p>记得<a href="http://weibo.com/jeffz" target="_blank" rel="external">@老赵</a>之前在微博上吐槽说，“有的人真是毫无长进，六年前某同事不会写程序输出全排列，昨天发邮件还是问我该怎么写，这时间浪费到我都看不下去了。” 那时候就很好奇全排列到底是什么东西，到底有多难？</p>
<p>今天复习的时候终于碰到这题了，结果果然自己太渣，看了好久都没明白，代码实现又是磕磕碰碰的。所以，就把它整理成笔记加深记忆，也希望能帮到和我一样的人。</p>
<h2 id="全排列">全排列</h2>
<p>所谓全排列，就是打印出字符串中所有字符的所有排列。例如输入字符串<code>abc</code>，则打印出 a、b、c 所能排列出来的所有字符串 <code>abc</code>、<code>acb</code>、<code>bac</code>、<code>bca</code>、<code>cab</code> 和 <code>cba</code> 。</p>
<p>一般最先想到的方法是暴力循环法，即对于每一位，遍历集合中可能的元素，如果在这一位之前出现过了该元素，跳过该元素。例如对于<code>abc</code>，第一位可以是 a 或 b 或 c 。当第一位为 a 时，第二位再遍历集合，发现 a 不行，因为前面已经出现 a 了，而 b 和 c 可以。当第二位为 b 时 ， 再遍历集合，发现 a 和 b 都不行，c 可以。可以用递归或循环来实现，但是复杂度为 $O(n^n)$ 。有没有更优雅的解法呢。</p>
<p>首先考虑<code>bac</code>和<code>cba</code>这二个字符串是如何得出的。显然这二个都是<code>abc</code>中的 a 与后面两字符交换得到的。然后可以将<code>abc</code>的第二个字符和第三个字符交换得到<code>acb</code>。同理可以根据<code>bac</code>和<code>cba</code>来得<code>bca</code>和<code>cab</code>。</p>
<p>因此可以知道 <strong>全排列就是从第一个数字起每个数分别与它后面的数字交换</strong>，也可以得出这种解法每次得到的结果都是正确结果，所以复杂度为 O(n!)。找到这个规律后，递归的代码就很容易写出来了：<br><a id="more"></a></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre>1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
</pre></td><td class="code"><pre><span class="preprocessor">#include&lt;stdio.h&gt;</span>
<span class="preprocessor">#include&lt;string&gt;</span>

<span class="comment">//交换两个字符</span>
<span class="keyword">void</span> Swap(<span class="keyword">char</span> *a ,<span class="keyword">char</span> *b)
{
	<span class="keyword">char</span> temp = *a;
	*a = *b;
	*b = temp;
}

<span class="comment">//递归全排列，start 为全排列开始的下标， length 为str数组的长度</span>
<span class="keyword">void</span> AllRange(<span class="keyword">char</span>* str,<span class="keyword">int</span> start,<span class="keyword">int</span> length)
{
	<span class="keyword">if</span>(start == length-<span class="number">1</span>)
	{
		<span class="built_in">printf</span>(<span class="string">"%s\n"</span>,str);
	}
	<span class="keyword">else</span>
	{
		<span class="keyword">for</span>(<span class="keyword">int</span> i=start;i&lt;=length-<span class="number">1</span>;i++)	
		{	<span class="comment">//从下标为start的数开始，分别与它后面的数字交换</span>
			Swap(&str[start],&str[i]); 
			AllRange(str,start+<span class="number">1</span>,length);
			Swap(&str[start],&str[i]); 
		}
	}
}

<span class="keyword">void</span> Permutation(<span class="keyword">char</span>* str)
{
	<span class="keyword">if</span>(str == NULL)
		<span class="keyword">return</span>;

	AllRange(str,<span class="number">0</span>,<span class="built_in">strlen</span>(str));
}

<span class="keyword">void</span> main()
{
	<span class="keyword">char</span> str[] = <span class="string">"abc"</span>;
	Permutation(str);
}
</pre></td></tr></table></figure>

<h2 id="去重的全排列">去重的全排列</h2>
<p>为了得到不一样的排列，可能我们最先想到的方法是当遇到和自己相同的就不交换了。如果我们输入的是<code>abb</code>，那么第一个字符与后面的交换后得到 <code>bab</code>、<code>bba</code>。然后<code>abb</code>中，第二个字符和第三个就不用交换了。但是对于<code>bab</code>，它的第二个字符和第三个是不同的，交换后得到<code>bba</code>，和之前的重复了。因此，这种方法不行。</p>
<p>因为<code>abb</code>能得到<code>bab</code>和<code>bba</code>，而<code>bab</code>又能得到<code>bba</code>，那我们能不能第一个<code>bba</code>不求呢？ 我们有了这种思路，第一个字符<code>a</code>与第二个字符<code>b</code>交换得到<code>bab</code>，然后考虑第一个字符<code>a</code>与第三个字符<code>b</code>交换，此时由于第三个字符等于第二个字符，所以它们不再交换。再考虑<code>bab</code>，它的第二个与第三个字符交换可以得到<code>bba</code>。此时全排列生成完毕，即<code>abb</code>、<code>bab</code>、<code>bba</code>三个。</p>
<p>这样我们也得到了在全排列中去掉重复的规则：<strong>去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换</strong>。用编程的话描述就是第i个数与第j个数交换时，要求[i,j)中没有与第j个数相等的数。下面给出完整代码：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre>1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
</pre></td><td class="code"><pre><span class="preprocessor">#include&lt;stdio.h&gt;</span>
<span class="preprocessor">#include&lt;string&gt;</span>

<span class="comment">//交换两个字符</span>
<span class="keyword">void</span> Swap(<span class="keyword">char</span> *a ,<span class="keyword">char</span> *b)
{
	<span class="keyword">char</span> temp = *a;
	*a = *b;
	*b = temp;
}

<span class="comment">//在 str 数组中，[start,end) 中是否有与 str[end] 元素相同的</span>
<span class="keyword">bool</span> IsSwap(<span class="keyword">char</span>* str,<span class="keyword">int</span> start,<span class="keyword">int</span> end)
{
	<span class="keyword">for</span>(;start&lt;end;start++)
	{
		<span class="keyword">if</span>(str[start] == str[end])
			<span class="keyword">return</span> <span class="keyword">false</span>;
	}
	<span class="keyword">return</span> <span class="keyword">true</span>;
}

<span class="comment">//递归去重全排列，start 为全排列开始的下标， length 为str数组的长度</span>
<span class="keyword">void</span> AllRange2(<span class="keyword">char</span>* str,<span class="keyword">int</span> start,<span class="keyword">int</span> length)
{
	<span class="keyword">if</span>(start == length-<span class="number">1</span>)
	{
		<span class="built_in">printf</span>(<span class="string">"%s\n"</span>,str);
	}
	<span class="keyword">else</span>
	{
		<span class="keyword">for</span>(<span class="keyword">int</span> i=start;i&lt;=length-<span class="number">1</span>;i++)
		{
			<span class="keyword">if</span>(IsSwap(str,start,i))
			{
				Swap(&str[start],&str[i]); 
				AllRange2(str,start+<span class="number">1</span>,length);
				Swap(&str[start],&str[i]); 
			}
		}
	}
}

<span class="keyword">void</span> Permutation(<span class="keyword">char</span>* str)
{
	<span class="keyword">if</span>(str == NULL)
		<span class="keyword">return</span>;

	AllRange2(str,<span class="number">0</span>,<span class="built_in">strlen</span>(str));
}

<span class="keyword">void</span> main()
{
	<span class="keyword">char</span> str[] = <span class="string">"abb"</span>;
	Permutation(str);
}
</pre></td></tr></table></figure>

<h2 id="全组合">全组合</h2>
<p>如果不是求字符的所有排列，而是求字符的所有组合应该怎么办呢？还是输入三个字符 a、b、c，则它们的组合有<code>a</code> <code>b</code> <code>c</code> <code>ab</code> <code>ac</code> <code>bc</code> <code>abc</code>。当然我们还是可以借鉴全排列的思路，利用问题分解的思路，最终用递归解决。不过这里介绍一种比较巧妙的思路 —— 基于位图。</p>
<p>假设原有元素 n 个，则最终组合结果是 $2^n-1$ 个。我们可以用位操作方法：假设元素原本有：a,b,c 三个，则 1 表示取该元素，0 表示不取。故取<code>a</code>则是<code>001</code>，取<code>ab</code>则是<code>011</code>。所以一共三位，每个位上有两个选择 0 和 1。而<code>000</code>没有意义，所以是$2^n-1$个结果。</p>
<p>这些结果的位图值都是 1,2…2^n-1。所以从值 1 到值 $2^n-1$ 依次输出结果：</p>
<p><code>001</code>,<code>010</code>,<code>011</code>,<code>100</code>,<code>101</code>,<code>110</code>,<code>111</code> 。对应输出组合结果为：<code>a</code>,<code>b</code>,<code>ab</code>,<code>c</code>,<code>ac</code>,<code>bc</code>,<code>abc</code>。<br>因此可以循环 1~2^n-1，然后输出对应代表的组合即可。有代码如下：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre>1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
</pre></td><td class="code"><pre><span class="preprocessor">#include&lt;stdio.h&gt;</span>
<span class="preprocessor">#include&lt;string.h&gt;</span>

<span class="keyword">void</span> Combination(<span class="keyword">char</span> *str)
{
	<span class="keyword">if</span>(str == NULL)
		<span class="keyword">return</span> ;
	<span class="keyword">int</span> len = <span class="built_in">strlen</span>(str);
	<span class="keyword">int</span> n = <span class="number">1</span>&lt;&lt;len;
	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;n;i++)    <span class="comment">//从 1 循环到 2^len -1</span>
	{
		<span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;len;j++)
		{
			<span class="keyword">int</span> temp = i;
			<span class="keyword">if</span>(temp & (<span class="number">1</span>&lt;&lt;j))   <span class="comment">//对应位上为1，则输出对应的字符</span>
			{
				<span class="built_in">printf</span>(<span class="string">"%c"</span>,*(str+j));
			}
		}
		<span class="built_in">printf</span>(<span class="string">"\n"</span>);
	}
}

<span class="keyword">void</span> main()
{
	<span class="keyword">char</span> str[] = <span class="string">"abc"</span>;
	Combination(str);
}
</pre></td></tr></table></figure>

<h2 id="参考资料">参考资料</h2>
<ul>
<li><a href="http://blog.csdn.net/morewindows/article/details/7370155" target="_blank" rel="external">MoreWindows-STL系列之十 全排列</a></li>
<li><a href="http://www.cnblogs.com/lifegoesonitself/p/3225803.html" target="_blank" rel="external">java 全组合 与全排列</a></li>
</ul>
<p>-EOF-</p>
  
	</div>
		<footer class="article-footer clearfix">
<div class="article-catetags">

<div class="article-categories">
  <span></span>
  <a class="article-category-link" href="/categories/程序设计/">程序设计</a>
</div>


  <div class="article-tags">
  
  <span></span> <a href="/tags/全排列/">全排列</a><a href="/tags/全组合/">全组合</a><a href="/tags/面试/">面试</a>
  </div>

</div>



	<div class="article-share" id="share">
	
	  <div data-url="http://wuchong.me/blog/2014/07/28/permutation-and-combination-realize/" data-title="全排列和全组合实现 | Jark&#39;s Blog" data-tsina="2176287895" class="share clearfix">
	  </div>
	
	</div>


</footer>

   	       
	</article>
	
<nav class="article-nav clearfix">
 
 <div class="prev" >
 <a href="/blog/2014/07/30/ali-bigdata-competition-write-to-the-5-monthes/" title="阿里推荐大赛：写给这五个月">
  <strong>上一篇：</strong><br/>
  <span>
  阿里推荐大赛：写给这五个月</span>
</a>
</div>


<div class="next">
<a href="/blog/2014/07/24/linux-process-manage/"  title="Linux基础：进程管理">
 <strong>下一篇：</strong><br/> 
 <span>Linux基础：进程管理
</span>
</a>
</div>

</nav>

	
<section id="comments" class="comment">
	<div class="ds-thread" data-thread-key="blog/2014/07/28/permutation-and-combination-realize/" data-title="全排列和全组合实现" data-url="http://wuchong.me/blog/2014/07/28/permutation-and-combination-realize/"></div>
</section>


</div>  
      <div class="openaside"><a class="navbutton" href="#" title="显示侧边栏"></a></div>

<div id="asidepart">
<div class="closeaside"><a class="closebutton" href="#" title="隐藏侧边栏"></a></div>
<aside class="clearfix">

  
<div class="categorieslist">
	<p class="asidetitle">分类</p>
		<ul>
		
			<li><a href="/categories/Hexo/" title="Hexo">Hexo<sup>7</sup></a></li>
		
			<li><a href="/categories/LinuxUnix/" title="Linux/Unix">Linux/Unix<sup>6</sup></a></li>
		
			<li><a href="/categories/Python/" title="Python">Python<sup>3</sup></a></li>
		
			<li><a href="/categories/推荐系统/" title="推荐系统">推荐系统<sup>3</sup></a></li>
		
			<li><a href="/categories/杂项资源/" title="杂项资源">杂项资源<sup>2</sup></a></li>
		
			<li><a href="/categories/程序设计/" title="程序设计">程序设计<sup>5</sup></a></li>
		
			<li><a href="/categories/系统架构/" title="系统架构">系统架构<sup>1</sup></a></li>
		
			<li><a href="/categories/编程语言/" title="编程语言">编程语言<sup>2</sup></a></li>
		
			<li><a href="/categories/职场生涯/" title="职场生涯">职场生涯<sup>2</sup></a></li>
		
			<li><a href="/categories/随笔生活/" title="随笔生活">随笔生活<sup>5</sup></a></li>
		
		</ul>
</div>


  
<div class="tagslist">
	<p class="asidetitle">标签</p>
		<ul class="clearfix">
		
			<li><a href="/tags/Hexo/" title="Hexo">Hexo<sup>8</sup></a></li>
		
			<li><a href="/tags/面试/" title="面试">面试<sup>5</sup></a></li>
		
			<li><a href="/tags/Linux基础/" title="Linux基础">Linux基础<sup>5</sup></a></li>
		
			<li><a href="/tags/生活/" title="生活">生活<sup>4</sup></a></li>
		
			<li><a href="/tags/博客/" title="博客">博客<sup>4</sup></a></li>
		
			<li><a href="/tags/Python/" title="Python">Python<sup>4</sup></a></li>
		
			<li><a href="/tags/阿里推荐大赛/" title="阿里推荐大赛">阿里推荐大赛<sup>4</sup></a></li>
		
			<li><a href="/tags/算法/" title="算法">算法<sup>2</sup></a></li>
		
			<li><a href="/tags/爬虫/" title="爬虫">爬虫<sup>2</sup></a></li>
		
			<li><a href="/tags/ODPS/" title="ODPS">ODPS<sup>2</sup></a></li>
		
			<li><a href="/tags/教程/" title="教程">教程<sup>2</sup></a></li>
		
			<li><a href="/tags/Jacman/" title="Jacman">Jacman<sup>2</sup></a></li>
		
			<li><a href="/tags/Java/" title="Java">Java<sup>2</sup></a></li>
		
			<li><a href="/tags/文件系统/" title="文件系统">文件系统<sup>2</sup></a></li>
		
			<li><a href="/tags/启动流程/" title="启动流程">启动流程<sup>1</sup></a></li>
		
			<li><a href="/tags/权限/" title="权限">权限<sup>1</sup></a></li>
		
			<li><a href="/tags/正则表达式/" title="正则表达式">正则表达式<sup>1</sup></a></li>
		
			<li><a href="/tags/jQuery/" title="jQuery">jQuery<sup>1</sup></a></li>
		
			<li><a href="/tags/双检锁/" title="双检锁">双检锁<sup>1</sup></a></li>
		
			<li><a href="/tags/设计模式/" title="设计模式">设计模式<sup>1</sup></a></li>
		
		</ul>
</div>


  <div class="linkslist">
  <p class="asidetitle">友情链接</p>
    <ul>
        
          <li>
            <a href="https://coderq.com" target="_blank" title="码农圈">码农圈</a>
          </li>
        
          <li>
            <a href="http://zipperary.com/" target="_blank" title="Zippera&#39;s Blog">Zippera&#39;s Blog</a>
          </li>
        
          <li>
            <a href="http://hijiangtao.github.io/" target="_blank" title="Data.Blog">Data.Blog</a>
          </li>
        
    </ul>
</div>

  <div class="weiboshow">
  <p class="asidetitle">新浪微博</p>
    <iframe width="100%" height="119" class="share_self"  frameborder="0" scrolling="no" src="http://widget.weibo.com/weiboshow/index.php?language=&width=0&height=119&fansRow=2&ptype=1&speed=0&skin=9&isTitle=1&noborder=1&isWeibo=0&isFans=0&uid=2176287895&verifier=b3593ceb&dpc=1"></iframe>
</div>


  <div class="rsspart">
	<a href="/atom.xml" target="_blank" title="rss">RSS 订阅</a>
</div>

</aside>
</div>
    </div>
    <footer><div id="footer" >
	
	<div class="line">
		<span></span>
		<div class="author"></div>
	</div>
	
	
	<section class="info">
		<p> Hello,I&#39;m WuChong. For now I&#39;m a graduate student in Beijing. <br/>
			I&#39;ll share my learning experience with you at this blog.</p>
	</section>
	 
	<div class="social-font" class="clearfix">
		
		<a href="http://weibo.com/wuchong1014" target="_blank" class="icon-weibo" title="微博"></a>
		
		
		<a href="https://github.com/wuchong" target="_blank" class="icon-github" title="github"></a>
		
		
		
		<a href="https://twitter.com/jarkwu" target="_blank" class="icon-twitter" title="twitter"></a>
		
		
		
		
		
		
		<a href="https://plus.google.com/111190881341800841449?rel=author" target="_blank" class="icon-google_plus" title="Google+"></a>
		
		
	</div>
		<p class="copyright">Powered by <a href="http://zespia.tw/hexo/" target="_blank" title="hexo">hexo</a> and Theme by <a href="https://github.com/wuchong/jacman" target="_blank" title="Pacman">Jacman</a> © 2014 
		
		<a href="http://wuchong.me/about" target="_blank" title="WuChong">WuChong</a>
		
		</p>
</div>
</footer>
    <script src="/js/jquery-2.0.3.min.js"></script>
<script src="/js/jquery.imagesloaded.min.js"></script>
<script src="/js/gallery.js"></script>

<script type="text/javascript">
$(document).ready(function(){ 
  $('.navbar').click(function(){
    $('header nav').toggleClass('shownav');
  });
  var myWidth = 0;
  function getSize(){
    if( typeof( window.innerWidth ) == 'number' ) {
      myWidth = window.innerWidth;
    } else if( document.documentElement && document.documentElement.clientWidth) {
      myWidth = document.documentElement.clientWidth;
    };
  };
  var m = $('#main'),
      a = $('#asidepart'),
      c = $('.closeaside'),
      o = $('.openaside');
  $(window).resize(function(){
    getSize(); 
    if (myWidth >= 1024) {
      $('header nav').removeClass('shownav');
    }else
    {
      m.removeClass('moveMain');
      a.css('display', 'block').removeClass('fadeOut');
      o.css('display', 'none');
        
    }
  });
  c.click(function(){
    a.addClass('fadeOut').css('display', 'none');
    o.css('display', 'block').addClass('fadeIn');
    m.addClass('moveMain');
  });
  o.click(function(){
    o.css('display', 'none').removeClass('beforeFadeIn');
    a.css('display', 'block').removeClass('fadeOut').addClass('fadeIn');      
    m.removeClass('moveMain');
  });
  $(window).scroll(function(){
    o.css("top",Math.max(80,260-$(this).scrollTop()));
  });
});
</script>

<script type="text/javascript">
$(document).ready(function(){ 
  var ai = $('.article-content>iframe'),
      ae = $('.article-content>embed'),
      t  = $('#toc'),
      h  = $('article h2')
      ah = $('article h2'),
      ta = $('#toc.toc-aside'),
      o  = $('.openaside'),
      c  = $('.closeaside');
  if(ai.length>0){
    ai.wrap('<div class="video-container" />');
  };
  if(ae.length>0){
   ae.wrap('<div class="video-container" />');
  };
  if(ah.length==0){
    t.css('display','none');
  }else{
    c.click(function(){
      ta.css('display', 'block').addClass('fadeIn');
    });
    o.click(function(){
      ta.css('display', 'none');
    });
    $(window).scroll(function(){
      ta.css("top",Math.max(140,320-$(this).scrollTop()));
    });
  };
});
</script>


<script type="text/javascript">
$(document).ready(function(){ 
  var $this = $('.share'),
      url = $this.attr('data-url'),
      encodedUrl = encodeURIComponent(url),
      title = $this.attr('data-title'),
      tsina = $this.attr('data-tsina'),
      description = $this.attr('description');
  var html = [
  '<a href="#" class="overlay" id="qrcode"></a>',
  '<div class="qrcode clearfix"><span>扫描二维码分享到微信朋友圈</span><a class="qrclose" href="#nothing"></a><strong>Loading...Please wait</strong><img id="qrcode-pic" data-src="http://s.jiathis.com/qrcode.php?url=' + encodedUrl + '"/></div>',
  '<a href="https://www.facebook.com/sharer.php?u=' + encodedUrl + '" class="article-share-facebook" target="_blank" title="Facebook"></a>',
  '<a href="https://twitter.com/intent/tweet?url=' + encodedUrl + '" class="article-share-twitter" target="_blank" title="Twitter"></a>',
  '<a href="#qrcode" class="article-share-qrcode" title="微信"></a>',
  '<a href="http://widget.renren.com/dialog/share?resourceUrl=' + encodedUrl + '&srcUrl=' + encodedUrl + '&title=' + title +'" class="article-share-renren" target="_blank" title="人人"></a>',
  '<a href="http://service.weibo.com/share/share.php?title='+title+'&url='+encodedUrl +'&ralateUid='+ tsina +'&searchPic=true&style=number' +'" class="article-share-weibo" target="_blank" title="微博"></a>',
  '<span title="Share to"></span>'
  ].join('');
  $this.append(html);
  $('.article-share-qrcode').click(function(){
    var imgSrc = $('#qrcode-pic').attr('data-src');
    $('#qrcode-pic').attr('src', imgSrc);
    $('#qrcode-pic').load(function(){
        $('.qrcode strong').text(' ');
    });
  });
});     
</script>



<script type="text/javascript">
  var duoshuoQuery = {short_name:"wuchong"};
  (function() {
    var ds = document.createElement('script');
    ds.type = 'text/javascript';ds.async = true;
    ds.src = '//static.duoshuo.com/embed.js';
    ds.charset = 'UTF-8';
    (document.getElementsByTagName('head')[0] 
    || document.getElementsByTagName('body')[0]).appendChild(ds);
  })();
</script> 







<link rel="stylesheet" href="/fancybox/jquery.fancybox.css" media="screen" type="text/css">
<script src="/fancybox/jquery.fancybox.pack.js"></script>
<script type="text/javascript">
$(document).ready(function(){ 
  $('.article-content').each(function(i){
    $(this).find('img').each(function(){
      if ($(this).parent().hasClass('fancybox')) return;
      var alt = this.alt;
      if (alt) $(this).after('<span class="caption">' + alt + '</span>');
      $(this).wrap('<a href="' + this.src + '" title="' + alt + '" class="fancybox"></a>');
    });
    $(this).find('.fancybox').each(function(){
      $(this).attr('rel', 'article' + i);
    });
  });
  if($.fancybox){
    $('.fancybox').fancybox();
  }
}); 
</script>



<!-- Analytics Begin -->

<script type="text/javascript">
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
  (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
  m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-46321946-2', 'wuchong.me');  
ga('send', 'pageview');
</script>





<!-- Analytics End -->

<!-- Totop Begin -->

	<div id="totop">
	<a title="返回顶部"><img src="/img/scrollup.png"/></a>
	</div>
	<script src="/js/totop.js"></script>

<!-- Totop End -->

<!-- MathJax Begin -->
<!-- mathjax config similar to math.stackexchange -->

<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    tex2jax: {
      inlineMath: [ ['$','$'], ["\\(","\\)"] ],
      processEscapes: true
    }
  });
</script>

<script type="text/x-mathjax-config">
    MathJax.Hub.Config({
      tex2jax: {
        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
      }
    });
</script>

<script type="text/x-mathjax-config">
    MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for(i=0; i < all.length; i += 1) {
            all[i].SourceElement().parentNode.className += ' has-jax';
        }
    });
</script>

<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>


<!-- MathJax End -->

  </body>
</html>
